//创建哈希表
public class MyHashBucket<K,V> {

    //创建节点
    public static class Node{

        Node next;
        int key;
        int val;

        //构造方法
        public Node(int key,int val){
            this.key = key;
            this.val = val;
        }
    }

    //定义成员变量
    Node[] arr;
    int size;

    public static int Init_Capacity = 5;
    public static double load_Factor = 0.75;

    public MyHashBucket(){
        arr = new Node[Init_Capacity];
        size = 0;
    }

    //增加
    public int put(int key,int val){
        //1.先查找原有桶中是否存在key，有就更新val
        int index = key % arr.length;
        Node curN;
        for(Node cur = arr[index];cur != null; cur = curN){
            if(cur.key == key){
                //更新
                int oldValue = cur.val;
                cur.val = val;
                size++;
                return oldValue;
            }
              curN = cur.next;
        }

        //原有的不存在key
       //创建一个形节点
        Node newNode = new Node(key,val);
        newNode.next = arr[index];
        arr[index] = newNode;
        size++;

        if(LoadFactor() >= load_Factor){
            add_Capacity();
        }
        return -1;
    }
      private void add_Capacity(){
         //1.二倍扩容
          Node[] newArrays = new Node[arr.length * 2];

          //2.将原有的数据重新存放
          for (int i = 0; i < arr.length; i++) {
              Node cur = arr[i];
              while(cur != null){
                  Node curN = cur.next;
                  int index = cur.key % newArrays.length;
                  cur.next = newArrays[index];
                  newArrays[index] = cur;
                  cur = curN;
              }
          }
          //3.赋值
          arr = newArrays;
      }
        private double LoadFactor(){
           return size * 1.0 / arr.length;
        }

        //get方法
    public int get(int key){
        //1.计算下标
        int index = key % arr.length;

        //2.循环遍历
        for (Node cur = arr[index]; cur != null ; cur = cur.next) {
            //找到了，返回val
            if(cur.key == key){
                return cur.val;
            }
        }
        //3.找不到
        return -1;
    }
}
